package 图;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 210. 课程表 II
 *现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，
 * 其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

 * 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
 * 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
 *
 * 思路：
 *  继续采用DFS的思路，构建邻接有向图， 判断是否成环，如果不成环则存在正确顺序，返回其中一个结果。
 *
 *  为了使用DFS解决课程表II问题，我们需要找到一种拓扑排序的顺序，并检测图中是否存在环。以下是详细的解题思路和代码实现：
 *
 * 解题思路
 * 1、构建邻接表：将课程之间的依赖关系转换为图的邻接表表示。对于每个先修条件[ai, bi]，表示必须完成课程bi才能学习ai，因此在邻接表中，bi指向ai。
 *
 * 2、DFS遍历检测环：使用深度优先搜索遍历图，同时跟踪每个节点的访问状态：
     * 0：未访问
     * 1：访问中（表示当前递归路径正在访问该节点，用于检测环）
     * 2：已访问
 *
 * 3、记录拓扑顺序：在DFS完成后，将节点加入结果列表。所有节点处理完毕后，将结果列表反转得到拓扑排序。
 *
 * 4、处理环的情况：如果在DFS过程中发现环，立即返回空数组。
 */
public class L_210 {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 1、构建邻接表
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        // 构建邻接表（bi -》 ai 的边） -- 保存每一个课程的所有先修课程，构建为一个有向图
        for (int[] prereq: prerequisites){
            int ai = prereq[0];
            int bi = prereq[1];
            adj.get(bi).add(ai);
        }

        int [] visited = new int[numCourses];
        List<Integer> result = new ArrayList<>();

        // 对每个节点进行dfs
        for (int i = 0; i < numCourses; i++) {
            // 如果节点存在环，证明不存在拓扑排序，返回空数组
            if (visited[i] == 0 && !dfs(i,adj, visited,result)){
                return new int[0];
            }
        }
        // 反转结果后输出
        Collections.reverse(result);
        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     *
     * @param node 当前节点下标
     * @param adj 邻接表
     * @param visited 标记节点是否访问过的数据
     * @param result 结果值
     * @return
     */
    private boolean dfs(int node, List<List<Integer>> adj, int[] visited, List<Integer> result){
        visited[node]=1; // 当前节点标记为访问中
        // 获取当前节点的邻接表
        for (int v : adj.get(node)){
            // 发现循环，返回false
            if (visited[v] == 1){
                return false;
            }else {
                // 如果邻接节点未被访问，递归调用dfs，递归存在环也返回false
                if (visited[v] == 0 && !dfs(v,adj,visited,result)){
                    return false;
                }
            }
        }
        // 标记当前节点为已访问，添加结果
        visited[node]=2;
        result.add(node);
        return true;
    }
}
